1. Field of the Invention
This invention relates to a method for increasing the speed of processing data in a computer system.
2. Description of the Related Art
In latter years, progress in VLSI (Very Large Scale Integrated) circuits has widened the gap in access times between microprocessors and memory devices. The memory devices are relatively slow compared with the rapid microprocessors. In order to narrow this gap in speed, caches have been introduced. These caches are installed between microprocessor and memory device. Caches are relatively small and quick memory devices in the form of chips. In one cache, for example, data that is often used by the microprocessor is stored. The cache fetches its data from a larger memory device, which is slow compared to the cache and the microprocessor. Sometimes, two or several caches are arranged hierarchically between a microprocessor and a large memory device.
Caches can also be found in multiprocessor systems, e.g., where each microprocessor is connected to a cache and where information can be stored into and retrieved from a large memory device by each cache.
An example of the use of this technique is a multiprocessor system in which different processors work to execute separate sections of a program and in which they therefore must fetch different data from the memory device. When a processor has completed one execution and is about to start a new one, it only needs a fraction of the data stored in the memory device. A processor in this situation first requests the cache for the first piece of data. If the cache does not have this piece of data, it fetches the data from the memory device and stores it in cache. As the processor requests data that is not stored in cache, the data contents of the cache increase. Since the processor is only executing a specific section of the program, the data sought by the processor will be found in cache more often as the execution advances, since the cache has already fetched these data upon previous requests from the processor. The access time for fetching a piece of data from the cache falls considerably short of the access time for the processor to fetch a piece of data straight from the large memory device. The speed of data between memory and processor is thus increased, decreasing the gap between memory-device speed and processor speed, which in turn increases data-processing speed.
Attempts have been made to further increase memory speed with a cache that, when fetching data at an address in the memory device would simultaneously fetch data at a nearby address in anticipation of the latter being requested by the processor, in which case that piece of data would already be in cache. Another possibility would be to fetch an entire block of data when a single piece is requested. This is advantageous if the data is stored in blocks allowing one to assume that, if the processor requests one address in a block, it will probably request several addresses in the same bock. This means that large amounts of unusable data are fetched however, which is why required caches increase in terms of necessary memory capacity, thus decreasing memory speed.